#include "../tools.h"
/**
 * 子集
 * 数组元素互不相同，输出所有的子集
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 
 * 回溯算法，最重要的是确定选择是什么
 * 因为这里的选择每次都固定为2个，当前数字在集合 or 不在集合，所以不需要使用循环，直接把两次情况列出来即可
 * 
 * 39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II
 */

class Solution {
public:
    void backtrack(vector<vector<int>> &res, vector<int> &path, const vector<int> &nums, int left){
        res.push_back(path);

        if (left >= nums.size()) return;
        
        for (int i = left; i < nums.size(); ++i){
            path.push_back(nums[i]);
            backtrack(res, path, nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size() == 0) return res;

        vector<int> path;
        backtrack(res, path, nums, 0);
        return res;
    }
};

int main(int argc, char const *argv[])
{

    vector<int> nums = {1,2,3};

    Solution s;
    auto res = s.subsets(nums);

    show(res);

    return 0;
}
